import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author hewei
 * @version 1.0
 * @description: 907. 子数组的最小值之和
 * @date 2022/9/6 15:28
 */

public class SumSubarrayMins {

    public static void main(String[] args) {
        SumSubarrayMins sumSubarrayMins = new SumSubarrayMins();
        int[] arr = {71,55,82,55};
        System.out.println(sumSubarrayMins.sumSubarrayMins(arr));
    }

    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] l = new int[n];
        int[] r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, n);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) r[stack.poll()] = i;
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) l[stack.poll()] = i;
            stack.push(i);
        }
        int mod = (int) (1e9 + 7);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (((long) (i - l[i]) * (r[i] - i) % mod) * arr[i]) % mod;
        }
        return (int) (ans % mod);
    }
}
